/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        438.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 14:47
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。
//
//字符串只包含小写英文字母，并且字符串s和 p的长度都不超过 20100。
//
//说明：
//
//字母异位词指字母相同，但排列不同的字符串。
//不考虑答案输出的顺序。
#include "../header.h"
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        unordered_map<char, int> gap; // 正数表示还需出现的次数，负数表示多出现的次数，0表示正好
        for (char c : p)
            gap[c]++;
        int left = 0, right = 0;// [left,right)
        while (right < s.size()) {
            char c = s[right++];
            gap[c]--; //入窗
            while (left < right && gap[c] < 0){
                gap[s[left++]]++; // 直到gap[c]==0
            }
            if (right - left == p.size())
                ans.push_back(left);
        }
        return ans;
    }
};
